//======================================================//
//							//
//	TRABALHO 3 DE PROGRAMACAO CONCORRENTE - 2013	//
//      GERADOR ALEATORIO DE PALAVRAS			//
//							//
//	GRUPO 11 - TURMA B:				//
//	Danilo Augusto Silva............6418678		//
//      Felipe Fukakusa.................6426976		//
//      Jader Bruno Pereira Lima........6792346		//
//							//
//======================================================//

//======================================================================================================================================//
//																	//
//	DESCRICAO:															//
//	Este trabalho gera aleatoriamente uma porcentagem das palavrras contidas em um texto de entrada					//
//																	//
//	Modo de execucao: 														//
//	(terminal linux) mpirun -np <numero de processos> ./palavrasAleatorias <texto_de_entrada.txt> <porcentagem_a_ser_gerada>	//
//																	//
//======================================================================================================================================//

//======================================//
//	      BIBLIOTECAS	        //
//======================================//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <sys/time.h>
#include <mpi.h>
#include <omp.h>
//======================================//

//======================================//
//	       DEFINICOES	        /
//======================================//
#define TRUE 1
#define FALSE 0
#define ROOT 0			//NUMERO DO PROCESSO RAIZ
#define TAMANHO_PALAVRA 5	//NUMERO MAXIMO DE LETRAS QUE PODEM SER GERADAS PARA UMA PALAVRA
#define MAX_LETRAS_PALAVRA 50 	//NUMERO MAXIMO DE LETRAS QUE UMA PALAVRA PODE TER
#define TAMANHO_BLOCO 100	//NUMERO DE PALAVRAS CONTIDAS NO BLOCO DE COMUNICACAO
#define MAX_PALAVRAS_ARQUIVO 5518000	//NUMERO DE PALAVRAS CONTIDAS NO BLOCO DE COMUNICACAO

//======================================//

//======================================================//
//	       ESTRUTURAS E VARIAVEIS GLOBAIS	        //
//======================================================//

//ESTRUTURA DE UMA PALAVRA
typedef struct{
	char texto[MAX_LETRAS_PALAVRA];
	int indice;
}Palavra;

//ESTRUTURA DE UM BLOCO
typedef struct{
	int inicio;
	int fim;
	int tamanho;
}Bloco;

//VETOR DE TODAS AS PALAVRAS DO ARQUIVO
char palavrasArquivo[MAX_PALAVRAS_ARQUIVO][MAX_LETRAS_PALAVRA];
int numPalavrasArquivo = 0;

int indicePalavrasGeradas[MAX_PALAVRAS_ARQUIVO];
int numPalavrasGeradas = 0;

int sequenciaPalavrasGeradas[MAX_PALAVRAS_ARQUIVO];
int sequenciaPalavras[MAX_PALAVRAS_ARQUIVO];

char todasPalavras[TAMANHO_PALAVRA*10][MAX_LETRAS_PALAVRA];

//CONTROLADORA MPI
MPI_Status status;
//======================================================//


//FUNCAO: verificaSubstring
//RETORNA TRUE(1) SE A STRING sub ESTIVER CONTIDA NA STRING string, A PARTIR DA POSICAO ini
//RETORNA FALSE(0) CASO CONTRARIO
int verificaSubstring(char *string, char *sub, int ini){
	int i = ini, j = 0;
	while(j < strlen(sub)){
		if((string[i] != sub[j])){ 
			return FALSE; 
		}
		else{ 
			j++;   
			i++;	  
		}
	}
	return TRUE;
}

//FUNCAO: geradorAleatorioPalavras
//Recebe uma palavra de um processo e gera aleatoriamente essa palavra, incrementado a quantidade de palavras geradas (qtdePalavrasGeradasSlave)
//Obs: esta funcao so gera palavras com tamanho ate MAX_TAMANHO_PALAVRA
void geradorAleatorioPalavras(char *palavra){
//VARIAVEIS:
	char palavraAleatoria[MAX_LETRAS_PALAVRA];
	int indice;
//FLAGS:
	int flagPalavraGerada = FALSE; //Nos diz se a palavra ja foi gerada
	int flagLetraGerada = FALSE; //Nos diz se a letra ja foi gerada
//CONTADORAS:
	int i;
//ESTRUTURAS:
	char letras[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//==============================================================//
	//TESTAR SE A PALAVRA JA FOI GERADA	

	//VARIAVEL ALEATORIA
	srand(time(NULL));
	//GERAR A PALAVRA
	//#pragma omp parallel private(i, indice, palavraAleatoria)
	while( !flagPalavraGerada ) {
		//PARA TODAS AS POSICOES DA PALAVRA
			
		for( i = 0; i < strlen(palavra); i++ ) {
			//GERAR A LETRA			
			while(!flagLetraGerada){			
				//GERA UM NUMERO ENTRE 0 E 26
				indice = rand()%26;
				//RECUPERA A LETRA DADO O INDICE GERADO ALEATOREAMENTE			
				palavraAleatoria[i] = letras[indice];
				//SE A LETRA GERADA FOR IGUAL A LETRA DA PALAVRA, PARA O WHILE  
				if(palavraAleatoria[i] == palavra[i]){
					flagLetraGerada = TRUE;
				}
			}
			flagLetraGerada = FALSE;
		}
		flagPalavraGerada = TRUE;

		palavraAleatoria[i] ='\0';
		
		//printf("PALAVRA GERADA: %s\n", palavraAleatoria);			
	} 

}

//FUNCAO PRINCIPAL
//RECEBE COMO PARAMETROS:
//	argv[1] = NOME DO TEXTO DE ENTRADA
//	argv[2] = PORCENTAGEM DAS PALAVRAS A SER GERADA
int main(int argc, char* argv[]){
//==================================================================//
//VARIAVEIS:
	int rank;	//Guarda o numero do processo atual
	int slave;	//Gerencia os escravos que estao sendo controlados pelo ROOT
	int numProcessos; //Quantidade de processos em execucao, definido na execucao do programa
	int qtdePalavrasGeradasSlave = 0;  //Numero de palavras geradas pelo slave ate serem mandadas para o ROOT
	int numBlocos = 0;
	char c;
	char palavra[MAX_LETRAS_PALAVRA];
	char palavraPequena[MAX_LETRAS_PALAVRA];
	int numPalavrasPequenas = 0;
	Bloco bloco;
	int tamanhoBloco;
	int tamanhoBlocoSlave;
	int k;
	int inicioSlave, fimSlave;
	Palavra palavrasBloco[TAMANHO_BLOCO];
	int palavrasGeradasSlave[TAMANHO_BLOCO];		

	FILE *file; //Arquivo de entrada
	struct timeval startTime;	//Tempo de inicio do processo
	struct timeval endTime;		//Tempo de final do processo		
//FLAGS:

//CONTADORAS:
	int i, j, iPalavra;
	char letras[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//==================================================================//
	//INICIA O CALCULO DO TEMPO
	gettimeofday( &startTime, NULL );
	double start = startTime.tv_sec + ( startTime.tv_usec / 1000000.0 );
	
	//INICIA O PARALELISMO
	MPI_Init ( &argc, &argv );

	//RECUPERA O NUMERO DE PROCESSOS E O RANK DO PROCESSO ATUAL
	MPI_Comm_size ( MPI_COMM_WORLD, &numProcessos );
	MPI_Comm_rank ( MPI_COMM_WORLD, &rank );
	MPI_Barrier(MPI_COMM_WORLD);

	//CARREGAR PALAVRAS NA MEMORIA
	if(rank == ROOT){
		int flagNovaPalavra;
		int iPalavrasBloco;
		int indicePalavrasGeradasSlave[TAMANHO_BLOCO];
		int qtdePalavrasNovas = 0;
		int numPalavrasPequenas = 0;
		int flagPalavraRepetida = FALSE;
		omp_set_num_threads(4);		
		if((file = fopen(argv[1], "r")) != NULL){
			iPalavra = 0;
			while (!feof(file)){			
				iPalavra = 0;				
				fscanf( file, "%c" , &c );
				while (!feof(file) && (c != '\r') && (c != '\n')){
					palavra[iPalavra++] = c;
					fscanf( file, "%c" , &c );
				}
				palavra[iPalavra] = '\0';
				if(strlen(palavra) > 5)	{

					numPalavrasPequenas = strlen(palavra)/TAMANHO_PALAVRA;
					
					for(i = 0; i < numPalavrasPequenas; i++){
						for(j = 0; j < TAMANHO_PALAVRA; j++){
							palavraPequena[j] = palavra[i*TAMANHO_PALAVRA + j];
						}
						palavraPequena[j+1] = '\0';
						strcpy(palavrasArquivo[numPalavrasArquivo], palavraPequena);
						sequenciaPalavras[numPalavrasArquivo++] = numPalavrasArquivo + 1;
						//printf("%s\n", palavraPequena);
					}

					
					j = 0;
					k = i*TAMANHO_PALAVRA;
					while(k < (strlen(palavra))){
						palavraPequena[j] = palavra[i*TAMANHO_PALAVRA + j];
	
						j++;
						k++;
					}
					palavraPequena[j] = '\0';
					if(strlen(palavraPequena) > 0){
						strcpy(palavrasArquivo[numPalavrasArquivo], palavraPequena);
						sequenciaPalavras[numPalavrasArquivo++] = 0;
						//printf("%s\n", palavraPequena);
					}
					else{
						sequenciaPalavras[numPalavrasArquivo - 1] = 0;
					}

				}
				else{								
						strcpy(palavrasArquivo[numPalavrasArquivo], palavra);
						sequenciaPalavras[numPalavrasArquivo++] = 0;
						
					
				}
						
				//printf("[p%d] PALAVRA %d: %s(%d)\n", rank, numPalavrasArquivo, palavra,strlen(palavra));
					
			}
			
			
			printf("numPalavrasArquivo = %d\n", numPalavrasArquivo);
			numBlocos = numPalavrasArquivo/TAMANHO_BLOCO;
			printf("numBlocos = %d\n", numBlocos);

			MPI_Bcast( &numBlocos, 1, MPI_INT, ROOT, MPI_COMM_WORLD ); 

			Bloco blocos[numBlocos + 1];

			


			for(i = 0; i < numBlocos; i++){
				blocos[i].inicio = i * TAMANHO_BLOCO;
				blocos[i].fim = (i + 1) * TAMANHO_BLOCO - 1;
				blocos[i].tamanho = TAMANHO_BLOCO;
			}
			blocos[i].inicio = i * TAMANHO_BLOCO;
			blocos[i].fim = numPalavrasArquivo;
			blocos[i].tamanho = blocos[i].fim - blocos[i].inicio;

			int X = numBlocos;
			int numPalavrasGeradas = 0;
			int K;	

			int porcentagem = 10;
			
			int flagNovaPalavra;		
			for(i = 0; i <= X; i++){

				//printf("numBlocos = %d, Bloco %d: inicio = %d, fim = %d, tamanho = %d\n", numBlocos, i, blocos[i].inicio, blocos[i].fim, blocos[i].tamanho);
								
				if(100*i >= numBlocos*(porcentagem))	{			
					//FINALIZA O CALCULO DO TEMPO DE CADA PORCENTAGEM
					gettimeofday( &endTime, NULL );
					double end = endTime.tv_sec + ( endTime.tv_usec / 1000000.0 );

					//IMPRIME O TEMPO DE EXECUCAO DE CADA PORCENTAGEM
					printf( "Tempo de execução para %d porcento de %.3lf segundos\n\n", porcentagem, end - start );
					porcentagem += 10;
				}
				
				iPalavrasBloco = 0;				
				for(j = blocos[i].inicio; j <= blocos[i].fim; j++){				
					strcpy(palavrasBloco[iPalavrasBloco].texto, palavrasArquivo[j]); 
					palavrasBloco[iPalavrasBloco++].indice = j;
				}
				MPI_Bcast( &blocos[i].tamanho, 1, MPI_INT, ROOT, MPI_COMM_WORLD );				
				MPI_Bcast( palavrasBloco, sizeof(Palavra)*blocos[i].tamanho, MPI_BYTE, ROOT, MPI_COMM_WORLD );

				for(slave = 1; slave < numProcessos; slave++){
					MPI_Recv( &qtdePalavrasGeradasSlave, 1, MPI_INT, slave, 1, MPI_COMM_WORLD, &status );
					//printf("ROOT recebeu de P%d - qtde = %d\n", slave, qtdePalavrasGeradasSlave);
					if(qtdePalavrasGeradasSlave != 0)					
						MPI_Recv(indicePalavrasGeradasSlave, qtdePalavrasGeradasSlave, MPI_INT, slave, 1, MPI_COMM_WORLD, &status);
									
					for(k = 0; k < qtdePalavrasGeradasSlave; k++){
						//printf("ROOT recebeu de P%d - qtde = %d\n", slave, qtdePalavrasGeradasSlave);
						flagNovaPalavra = TRUE;						
						/*	
						for(j = 0; j < numPalavrasGeradas/100; j++){
							if(!strcmp(	palavrasArquivo[indicePalavrasGeradas[j]], 										palavrasArquivo[indicePalavrasGeradasSlave[k]])){
																			
								if(sequenciaPalavras[indicePalavrasGeradas[j]] != 0){	
									flagNovaPalavra = TRUE;
									break;
								}
								else{
									flagNovaPalavra = FALSE;
									break;
								}
								
							
							}
						}
						*/						
						if(flagNovaPalavra){
							qtdePalavrasNovas++;								
							indicePalavrasGeradas[numPalavrasGeradas] = indicePalavrasGeradasSlave[k];
							sequenciaPalavrasGeradas[numPalavrasGeradas] = sequenciaPalavras[indicePalavrasGeradasSlave[k]];
							
							numPalavrasGeradas++;
							//printf("PALAVRA GERADA SLAVE %d: %s seq = %d\n", slave, palavrasArquivo[indicePalavrasGeradasSlave[k]], sequenciaPalavras[indicePalavrasGeradasSlave[k]]);						
						}
						
					}
					MPI_Send( &qtdePalavrasNovas, 1, MPI_INT, slave,1, MPI_COMM_WORLD );
					qtdePalavrasNovas = 0;
				}
			}

		}
		else{
			printf("ERRO: Arquivo nao encontrado\n");
			exit(1);
		}
	}
	else{
		MPI_Bcast( &numBlocos, 1, MPI_INT, ROOT, MPI_COMM_WORLD );
		int iPalavrasBloco;
		int indicePalavrasGeradasSlave[TAMANHO_BLOCO];
		int qtdePalavrasNovas;
		int flagNovaPalavra;
		int totalPalavrasGeradasSlave = 0;
			
		 		
		for(i = 0; i <= numBlocos; i++){		
			MPI_Bcast( &tamanhoBloco, 1, MPI_INT, ROOT, MPI_COMM_WORLD ); 		
			MPI_Bcast( palavrasBloco, sizeof(Palavra)*tamanhoBloco, MPI_BYTE, ROOT, MPI_COMM_WORLD ); 
						
			
			inicioSlave = (rank - 1)*tamanhoBloco/(numProcessos - 1);
			fimSlave = (rank)*tamanhoBloco/(numProcessos - 1) - 1;


			qtdePalavrasGeradasSlave = 0;
			for(j = inicioSlave; j <= fimSlave; j++){
				if(strlen(palavrasBloco[j].texto) <= TAMANHO_PALAVRA){			
					flagNovaPalavra = TRUE;					
										
					if(flagNovaPalavra)	{				
						geradorAleatorioPalavras(palavrasBloco[j].texto);
						indicePalavrasGeradasSlave[qtdePalavrasGeradasSlave] = palavrasBloco[j].indice;
						qtdePalavrasGeradasSlave += 1;					
						}				
				}
			}
			MPI_Send( &qtdePalavrasGeradasSlave, 1, MPI_INT, ROOT, 1, MPI_COMM_WORLD );
			if(qtdePalavrasGeradasSlave != 0)			
				MPI_Send( indicePalavrasGeradasSlave, qtdePalavrasGeradasSlave, MPI_INT, ROOT, 1, MPI_COMM_WORLD );

			MPI_Recv( &qtdePalavrasNovas, 1, MPI_INT, ROOT,	1, MPI_COMM_WORLD, &status);		
			totalPalavrasGeradasSlave += qtdePalavrasGeradasSlave;
			

		}

		//PROCESSAR PALAVRAS MAIORES QUE 5 LETRAS
		printf( "Slave%d - Numero de palavras geradas: %d\n", rank, totalPalavrasGeradasSlave );
	}

	//FINALIZA O CALCULO DO TEMPO
	gettimeofday( &endTime, NULL );
	double end = endTime.tv_sec + ( endTime.tv_usec / 1000000.0 );

	//IMPRIME O TEMPO DE EXECUCAO DO PROCESSO
	
	printf( "Tempo de execução do processo: %d eh de %.3lf segundos\n\n", rank, end - start );

	//FINALIZA O MPI
	MPI_Finalize();
	return EXIT_SUCCESS;
}//main



